package offer2

/**
原题链接:
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=fkosbmj

B站 小美算法讲解
剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1   4
\
2
输出: 4
*/

//思路：中序遍历，返回list的第n-1元素即可

func findTargetNode(root *TreeNode, k int) int {
	list := make([]int, 0) //声明中序遍历数组
	inorder(root, &list)   //进行中序遍历

	return list[len(list)-k] //返回第k大的元素
}

// 中序遍历
func inorder(root *TreeNode, list *[]int) {
	if root == nil { //如果根节点为nil,直接返回一个空数组即可
		return
	}

	inorder(root.Left, list)        // 递归开始，递归左子树
	*list = append(*list, root.Val) // 处理根节点，加入list
	inorder(root.Right, list)       // 递归

	// 右子树
}
